# 寻找两个正序数组的中位数: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/


# 1. 最简单能想到的
class Solution:
    def findMedianSortedArrays(self, nums1: list, nums2: list) -> float:
        """ 合并排序的方式实现，合并为一个有序数组，再找到中位数 
            合并排序，空间复杂度O（m+n），时间复杂度O(m + n)
        """
        n, m = len(nums1), len(nums2)
        temp = [0] * (n + m)
        i = j = k = 0
        while i < n and j < m:
            if nums1[i] < nums2[j]:
                temp[k] = nums1[i]
                i += 1
            else:
                temp[k] = nums2[j]
                j += 1
            k += 1
        
        while i < n: 
            temp[k] = nums1[i]
            i += 1
            k += 1
        
        while j < m:
            temp[k] = nums2[j]
            j += 1
            k += 1

        print(temp)
        return temp[(m + n) // 2] if (m + n) % 2 == 1 else (temp[(m + n) // 2 - 1] + temp[(m + n) // 2]) / 2


# 解法1 的for循环解法，代码更加简便
class Solution:
    def findMedianSortedArrays(self, nums1: list, nums2: list) -> float:
        """ 合并排序的方式实现，合并为一个有序数组，再找到中位数 """
        n, m = len(nums1), len(nums2)
        temp = [0] * (n + m)
        i = j = k = 0
        for k in range(n + m):
            if i < n and (j >= m or nums1[i] < nums2[j]):
                temp[k] = nums1[i]
                i += 1
            else:
                temp[k] = nums2[j]
                j += 1
        
        return temp[(m + n) // 2] if (m + n) % 2 == 1 else (temp[(m + n) // 2 - 1] + temp[(m + n) // 2]) / 2



# 2. 对上面进行优化。双指针，使用变量代替 temp数组，优化空间
class Solution:
    def findMedianSortedArrays(self, nums1: list, nums2: list) -> float:
        """ 
            在合并排序的基础上优化空间复杂度， 其实我们只需要知道中位数的元素是哪个即可，根本不需要保存排序后的数组
            使用两个指针遍历 nums1， nums2 即可， 另一个变量用来记录位置
            注意： 为了同一 奇数和偶数的 中位数算法，同一选取两个数字相加 除2作为计算, 下标分别为：
            middleleft = (n + m - 1) // 2
            middleRight = (n + m) // 2
            奇数下标相同，偶数不同。 偶数除以2 和偶数加1除以2结果不变
        """
        n, m = len(nums1), len(nums2)
        middleLeft = (n + m - 1) // 2
        middleRight = (n + m) // 2
        total = temp = 0
        i = j = 0
        for k in range(n + m):
            # 这里要注意！j >= m 放到前面，当 i < n,  j >= m 或 nums1[i] < nums2[j] 都执行 i， 否则执行 j
            if i < n and (j >= m or nums1[i] < nums2[j]):
                temp = nums1[i]
                i += 1
            else: 
                temp = nums2[j]
                j += 1
            
            if k == middleLeft: total += temp 
            if k == middleRight: 
                total += temp
                # 直接break，已经找到中间两个数的和
                break

        return total / 2
